home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / include / xfs / xfs_da_btree.h < prev    next >
C/C++ Source or Header  |  2005-10-18  |  13KB  |  336 lines
  1. /*
  2.  * Copyright (c) 2000, 2002 Silicon Graphics, Inc.  All Rights Reserved.
  3.  *
  4.  * This program is free software; you can redistribute it and/or modify it
  5.  * under the terms of version 2 of the GNU General Public License as
  6.  * published by the Free Software Foundation.
  7.  *
  8.  * This program is distributed in the hope that it would be useful, but
  9.  * WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11.  *
  12.  * Further, this software is distributed without any warranty that it is
  13.  * free of the rightful claim of any third person regarding infringement
  14.  * or the like.  Any license provided herein, whether implied or
  15.  * otherwise, applies only to this software file.  Patent licenses, if
  16.  * any, provided herein do not apply to combinations of this program with
  17.  * other software, or any other product whatsoever.
  18.  *
  19.  * You should have received a copy of the GNU General Public License along
  20.  * with this program; if not, write the Free Software Foundation, Inc., 59
  21.  * Temple Place - Suite 330, Boston MA 02111-1307, USA.
  22.  *
  23.  * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
  24.  * Mountain View, CA  94043, or:
  25.  *
  26.  * http://www.sgi.com
  27.  *
  28.  * For further information regarding this notice, see:
  29.  *
  30.  * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
  31.  */
  32. #ifndef __XFS_DA_BTREE_H__
  33. #define    __XFS_DA_BTREE_H__
  34.  
  35. struct xfs_buf;
  36. struct xfs_bmap_free;
  37. struct xfs_inode;
  38. struct xfs_mount;
  39. struct xfs_trans;
  40. struct zone;
  41.  
  42. /*========================================================================
  43.  * Directory Structure when greater than XFS_LBSIZE(mp) bytes.
  44.  *========================================================================*/
  45.  
  46. /*
  47.  * This structure is common to both leaf nodes and non-leaf nodes in the Btree.
  48.  *
  49.  * Is is used to manage a doubly linked list of all blocks at the same
  50.  * level in the Btree, and to identify which type of block this is.
  51.  */
  52. #define XFS_DA_NODE_MAGIC    0xfebe    /* magic number: non-leaf blocks */
  53. #define XFS_DIR_LEAF_MAGIC    0xfeeb    /* magic number: directory leaf blks */
  54. #define XFS_ATTR_LEAF_MAGIC    0xfbee    /* magic number: attribute leaf blks */
  55. #define    XFS_DIR2_LEAF1_MAGIC    0xd2f1    /* magic number: v2 dirlf single blks */
  56. #define    XFS_DIR2_LEAFN_MAGIC    0xd2ff    /* magic number: v2 dirlf multi blks */
  57.  
  58. #define    XFS_DIRX_LEAF_MAGIC(mp)    \
  59.     (XFS_DIR_IS_V1(mp) ? XFS_DIR_LEAF_MAGIC : XFS_DIR2_LEAFN_MAGIC)
  60.  
  61. typedef struct xfs_da_blkinfo {
  62.     xfs_dablk_t forw;            /* previous block in list */
  63.     xfs_dablk_t back;            /* following block in list */
  64.     __uint16_t magic;            /* validity check on block */
  65.     __uint16_t pad;                /* unused */
  66. } xfs_da_blkinfo_t;
  67.  
  68. /*
  69.  * This is the structure of the root and intermediate nodes in the Btree.
  70.  * The leaf nodes are defined above.
  71.  *
  72.  * Entries are not packed.
  73.  *
  74.  * Since we have duplicate keys, use a binary search but always follow
  75.  * all match in the block, not just the first match found.
  76.  */
  77. #define    XFS_DA_NODE_MAXDEPTH    5    /* max depth of Btree */
  78.  
  79. typedef struct xfs_da_intnode {
  80.     struct xfs_da_node_hdr {    /* constant-structure header block */
  81.         xfs_da_blkinfo_t info;    /* block type, links, etc. */
  82.         __uint16_t count;    /* count of active entries */
  83.         __uint16_t level;    /* level above leaves (leaf == 0) */
  84.     } hdr;
  85.     struct xfs_da_node_entry {
  86.         xfs_dahash_t hashval;    /* hash value for this descendant */
  87.         xfs_dablk_t before;    /* Btree block before this key */
  88.     } btree[1];            /* variable sized array of keys */
  89. } xfs_da_intnode_t;
  90. typedef struct xfs_da_node_hdr xfs_da_node_hdr_t;
  91. typedef struct xfs_da_node_entry xfs_da_node_entry_t;
  92.  
  93. #define XFS_DA_MAXHASH    ((xfs_dahash_t)-1) /* largest valid hash value */
  94.  
  95. /*
  96.  * Macros used by directory code to interface to the filesystem.
  97.  */
  98. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_LBSIZE)
  99. int xfs_lbsize(struct xfs_mount *mp);
  100. #define    XFS_LBSIZE(mp)            xfs_lbsize(mp)
  101. #else
  102. #define    XFS_LBSIZE(mp)    ((mp)->m_sb.sb_blocksize)
  103. #endif
  104. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_LBLOG)
  105. int xfs_lblog(struct xfs_mount *mp);
  106. #define    XFS_LBLOG(mp)            xfs_lblog(mp)
  107. #else
  108. #define    XFS_LBLOG(mp)    ((mp)->m_sb.sb_blocklog)
  109. #endif
  110.  
  111. /*
  112.  * Macros used by directory code to interface to the kernel
  113.  */
  114.  
  115. /*
  116.  * Macros used to manipulate directory off_t's
  117.  */
  118. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_DA_MAKE_BNOENTRY)
  119. __uint32_t xfs_da_make_bnoentry(struct xfs_mount *mp, xfs_dablk_t bno,
  120.                 int entry);
  121. #define    XFS_DA_MAKE_BNOENTRY(mp,bno,entry)    \
  122.     xfs_da_make_bnoentry(mp,bno,entry)
  123. #else
  124. #define    XFS_DA_MAKE_BNOENTRY(mp,bno,entry) \
  125.     (((bno) << (mp)->m_dircook_elog) | (entry))
  126. #endif
  127. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_DA_MAKE_COOKIE)
  128. xfs_off_t xfs_da_make_cookie(struct xfs_mount *mp, xfs_dablk_t bno, int entry,
  129.                 xfs_dahash_t hash);
  130. #define    XFS_DA_MAKE_COOKIE(mp,bno,entry,hash)    \
  131.     xfs_da_make_cookie(mp,bno,entry,hash)
  132. #else
  133. #define    XFS_DA_MAKE_COOKIE(mp,bno,entry,hash) \
  134.     (((xfs_off_t)XFS_DA_MAKE_BNOENTRY(mp, bno, entry) << 32) | (hash))
  135. #endif
  136. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_DA_COOKIE_HASH)
  137. xfs_dahash_t xfs_da_cookie_hash(struct xfs_mount *mp, xfs_off_t cookie);
  138. #define    XFS_DA_COOKIE_HASH(mp,cookie)        xfs_da_cookie_hash(mp,cookie)
  139. #else
  140. #define    XFS_DA_COOKIE_HASH(mp,cookie)    ((xfs_dahash_t)(cookie))
  141. #endif
  142. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_DA_COOKIE_BNO)
  143. xfs_dablk_t xfs_da_cookie_bno(struct xfs_mount *mp, xfs_off_t cookie);
  144. #define    XFS_DA_COOKIE_BNO(mp,cookie)        xfs_da_cookie_bno(mp,cookie)
  145. #else
  146. #define    XFS_DA_COOKIE_BNO(mp,cookie) \
  147.     (((xfs_off_t)(cookie) >> 31) == -1LL ? \
  148.         (xfs_dablk_t)0 : \
  149.         (xfs_dablk_t)((xfs_off_t)(cookie) >> ((mp)->m_dircook_elog + 32)))
  150. #endif
  151. #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_DA_COOKIE_ENTRY)
  152. int xfs_da_cookie_entry(struct xfs_mount *mp, xfs_off_t cookie);
  153. #define    XFS_DA_COOKIE_ENTRY(mp,cookie)        xfs_da_cookie_entry(mp,cookie)
  154. #else
  155. #define    XFS_DA_COOKIE_ENTRY(mp,cookie) \
  156.     (((xfs_off_t)(cookie) >> 31) == -1LL ? \
  157.         (xfs_dablk_t)0 : \
  158.         (xfs_dablk_t)(((xfs_off_t)(cookie) >> 32) & \
  159.                   ((1 << (mp)->m_dircook_elog) - 1)))
  160. #endif
  161.  
  162.  
  163. /*========================================================================
  164.  * Btree searching and modification structure definitions.
  165.  *========================================================================*/
  166.  
  167. /*
  168.  * Structure to ease passing around component names.
  169.  */
  170. typedef struct xfs_da_args {
  171.     uchar_t        *name;        /* string (maybe not NULL terminated) */
  172.     int        namelen;    /* length of string (maybe no NULL) */
  173.     uchar_t        *value;        /* set of bytes (maybe contain NULLs) */
  174.     int        valuelen;    /* length of value */
  175.     int        flags;        /* argument flags (eg: ATTR_NOCREATE) */
  176.     xfs_dahash_t    hashval;    /* hash value of name */
  177.     xfs_ino_t    inumber;    /* input/output inode number */
  178.     struct xfs_inode *dp;        /* directory inode to manipulate */
  179.     xfs_fsblock_t    *firstblock;    /* ptr to firstblock for bmap calls */
  180.     struct xfs_bmap_free *flist;    /* ptr to freelist for bmap_finish */
  181.     struct xfs_trans *trans;    /* current trans (changes over time) */
  182.     xfs_extlen_t    total;        /* total blocks needed, for 1st bmap */
  183.     int        whichfork;    /* data or attribute fork */
  184.     xfs_dablk_t    blkno;        /* blkno of attr leaf of interest */
  185.     int        index;        /* index of attr of interest in blk */
  186.     xfs_dablk_t    rmtblkno;    /* remote attr value starting blkno */
  187.     int        rmtblkcnt;    /* remote attr value block count */
  188.     xfs_dablk_t    blkno2;        /* blkno of 2nd attr leaf of interest */
  189.     int        index2;        /* index of 2nd attr in blk */
  190.     xfs_dablk_t    rmtblkno2;    /* remote attr value starting blkno */
  191.     int        rmtblkcnt2;    /* remote attr value block count */
  192.     unsigned char    justcheck;    /* T/F: check for ok with no space */
  193.     unsigned char    rename;        /* T/F: this is an atomic rename op */
  194.     unsigned char    addname;    /* T/F: this is an add operation */
  195.     unsigned char    oknoent;    /* T/F: ok to return ENOENT, else die */
  196. } xfs_da_args_t;
  197.  
  198. /*
  199.  * Structure to describe buffer(s) for a block.
  200.  * This is needed in the directory version 2 format case, when
  201.  * multiple non-contiguous fsblocks might be needed to cover one
  202.  * logical directory block.
  203.  * If the buffer count is 1 then the data pointer points to the
  204.  * same place as the b_addr field for the buffer, else to kmem_alloced memory.
  205.  */
  206. typedef struct xfs_dabuf {
  207.     int        nbuf;        /* number of buffer pointers present */
  208.     short        dirty;        /* data needs to be copied back */
  209.     short        bbcount;    /* how large is data in bbs */
  210.     void        *data;        /* pointer for buffers' data */
  211. #ifdef XFS_DABUF_DEBUG
  212.     inst_t        *ra;        /* return address of caller to make */
  213.     struct xfs_dabuf *next;        /* next in global chain */
  214.     struct xfs_dabuf *prev;        /* previous in global chain */
  215.     struct xfs_buftarg *target;    /* device for buffer */
  216.     xfs_daddr_t    blkno;        /* daddr first in bps[0] */
  217. #endif
  218.     struct xfs_buf    *bps[1];    /* actually nbuf of these */
  219. } xfs_dabuf_t;
  220. #define    XFS_DA_BUF_SIZE(n)    \
  221.     (sizeof(xfs_dabuf_t) + sizeof(struct xfs_buf *) * ((n) - 1))
  222.  
  223. #ifdef XFS_DABUF_DEBUG
  224. extern xfs_dabuf_t    *xfs_dabuf_global_list;
  225. #endif
  226.  
  227. /*
  228.  * Storage for holding state during Btree searches and split/join ops.
  229.  *
  230.  * Only need space for 5 intermediate nodes.  With a minimum of 62-way
  231.  * fanout to the Btree, we can support over 900 million directory blocks,
  232.  * which is slightly more than enough.
  233.  */
  234. typedef struct xfs_da_state_blk {
  235.     xfs_dabuf_t    *bp;        /* buffer containing block */
  236.     xfs_dablk_t    blkno;        /* filesystem blkno of buffer */
  237.     xfs_daddr_t    disk_blkno;    /* on-disk blkno (in BBs) of buffer */
  238.     int        index;        /* relevant index into block */
  239.     xfs_dahash_t    hashval;    /* last hash value in block */
  240.     int        magic;        /* blk's magic number, ie: blk type */
  241. } xfs_da_state_blk_t;
  242.  
  243. typedef struct xfs_da_state_path {
  244.     int            active;        /* number of active levels */
  245.     xfs_da_state_blk_t    blk[XFS_DA_NODE_MAXDEPTH];
  246. } xfs_da_state_path_t;
  247.  
  248. typedef struct xfs_da_state {
  249.     xfs_da_args_t        *args;        /* filename arguments */
  250.     struct xfs_mount    *mp;        /* filesystem mount point */
  251.     unsigned int        blocksize;    /* logical block size */
  252.     unsigned int        node_ents;    /* how many entries in danode */
  253.     xfs_da_state_path_t    path;        /* search/split paths */
  254.     xfs_da_state_path_t    altpath;    /* alternate path for join */
  255.     unsigned char        inleaf;        /* insert into 1->lf, 0->splf */
  256.     unsigned char        extravalid;    /* T/F: extrablk is in use */
  257.     unsigned char        extraafter;    /* T/F: extrablk is after new */
  258.     xfs_da_state_blk_t    extrablk;    /* for double-splits on leafs */
  259.                         /* for dirv2 extrablk is data */
  260. } xfs_da_state_t;
  261.  
  262. /*
  263.  * Utility macros to aid in logging changed structure fields.
  264.  */
  265. #define XFS_DA_LOGOFF(BASE, ADDR)    ((char *)(ADDR) - (char *)(BASE))
  266. #define XFS_DA_LOGRANGE(BASE, ADDR, SIZE)    \
  267.         (uint)(XFS_DA_LOGOFF(BASE, ADDR)), \
  268.         (uint)(XFS_DA_LOGOFF(BASE, ADDR)+(SIZE)-1)
  269.  
  270.  
  271. #ifdef __KERNEL__
  272. /*========================================================================
  273.  * Function prototypes for the kernel.
  274.  *========================================================================*/
  275.  
  276. /*
  277.  * Routines used for growing the Btree.
  278.  */
  279. int    xfs_da_node_create(xfs_da_args_t *args, xfs_dablk_t blkno, int level,
  280.                      xfs_dabuf_t **bpp, int whichfork);
  281. int    xfs_da_split(xfs_da_state_t *state);
  282.  
  283. /*
  284.  * Routines used for shrinking the Btree.
  285.  */
  286. int    xfs_da_join(xfs_da_state_t *state);
  287. void    xfs_da_fixhashpath(xfs_da_state_t *state,
  288.                       xfs_da_state_path_t *path_to_to_fix);
  289.  
  290. /*
  291.  * Routines used for finding things in the Btree.
  292.  */
  293. int    xfs_da_node_lookup_int(xfs_da_state_t *state, int *result);
  294. int    xfs_da_path_shift(xfs_da_state_t *state, xfs_da_state_path_t *path,
  295.                      int forward, int release, int *result);
  296. /*
  297.  * Utility routines.
  298.  */
  299. int    xfs_da_blk_unlink(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
  300.                      xfs_da_state_blk_t *save_blk);
  301. int    xfs_da_blk_link(xfs_da_state_t *state, xfs_da_state_blk_t *old_blk,
  302.                        xfs_da_state_blk_t *new_blk);
  303.  
  304. /*
  305.  * Utility routines.
  306.  */
  307. int    xfs_da_grow_inode(xfs_da_args_t *args, xfs_dablk_t *new_blkno);
  308. int    xfs_da_get_buf(struct xfs_trans *trans, struct xfs_inode *dp,
  309.                   xfs_dablk_t bno, xfs_daddr_t mappedbno,
  310.                   xfs_dabuf_t **bp, int whichfork);
  311. int    xfs_da_read_buf(struct xfs_trans *trans, struct xfs_inode *dp,
  312.                    xfs_dablk_t bno, xfs_daddr_t mappedbno,
  313.                    xfs_dabuf_t **bpp, int whichfork);
  314. xfs_daddr_t    xfs_da_reada_buf(struct xfs_trans *trans, struct xfs_inode *dp,
  315.             xfs_dablk_t bno, int whichfork);
  316. int    xfs_da_shrink_inode(xfs_da_args_t *args, xfs_dablk_t dead_blkno,
  317.                       xfs_dabuf_t *dead_buf);
  318.  
  319. uint xfs_da_hashname(uchar_t *name_string, int name_length);
  320. uint xfs_da_log2_roundup(uint i);
  321. xfs_da_state_t *xfs_da_state_alloc(void);
  322. void xfs_da_state_free(xfs_da_state_t *state);
  323. void xfs_da_state_kill_altpath(xfs_da_state_t *state);
  324.  
  325. void xfs_da_buf_done(xfs_dabuf_t *dabuf);
  326. void xfs_da_log_buf(struct xfs_trans *tp, xfs_dabuf_t *dabuf, uint first,
  327.                uint last);
  328. void xfs_da_brelse(struct xfs_trans *tp, xfs_dabuf_t *dabuf);
  329. void xfs_da_binval(struct xfs_trans *tp, xfs_dabuf_t *dabuf);
  330. xfs_daddr_t xfs_da_blkno(xfs_dabuf_t *dabuf);
  331.  
  332. extern struct kmem_zone *xfs_da_state_zone;
  333. #endif    /* __KERNEL__ */
  334.  
  335. #endif    /* __XFS_DA_BTREE_H__ */
  336.